package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

/**
 * 正则匹配
 *
 * @author Administrator
 * @date 2020/6/3 16:33
 */
public class RegularMatch {
    /**
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
     * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * 说明:
     * s 可能为空，且只包含从 a-z 的小写字母。
     * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
     */
    @Test
    public void test() {
        Assert.assertTrue(isMatch("ab", ".*"));
        Assert.assertFalse(isMatch("ab", ".*c"));
        Assert.assertTrue(isMatch("aa", "a*"));
        Assert.assertTrue(isMatch("aaa", "a*a"));
        Assert.assertFalse(isMatch("aa", "a"));
        Assert.assertTrue(isMatch("aab", "c*a*b"));
        Assert.assertFalse(isMatch("mississippi", "mis*is*p*."));
    }

    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;
        for (int i = s.length(); i >= 0; i--) {
            for (int j = p.length() - 1; j >= 0; j--) {
                boolean first_match = (i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    // 正则的指针不在最后一位 并且 下一位是个*
                    // 则下一位非*的匹配结果为true（此时*=0） 或者 当前匹配结果结果为true并且下一个字符也匹配为true（j+1=*）
                    dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
                } else {
                    // 当前匹配结果结果为true并且下一个字符也匹配为true
                    dp[i][j] = first_match && dp[i + 1][j + 1];
                }
            }
        }

        return dp[0][0];
    }
}
